import java.util.ArrayList;

class Task {
	int id;
	int time;
	String name;
	int manpower;
	Task[] deps;
	ArrayList<Task> tasksWhichDepend = new ArrayList<>();

	boolean timesCalculated = false;
	int earliestStart = -1;
	int latestStart = -1;
	int slack = 0;
	int earliestFinished = -1;
	int startIndex = -1;

	ArrayList<Task> findCycle(ArrayList<Task> seen) {
		seen = new ArrayList<Task>(seen);
		seen.add(this);
		for (Task dep: deps) {
			ArrayList<Task> nseen = new ArrayList<Task>(seen);

			if (nseen.contains(dep)) {
				ArrayList<Task> l = new ArrayList<>();
				l.add(dep);
				l.add(this);
				return l;
			}

			ArrayList<Task> l = dep.findCycle(seen);
			if (l != null) {
				l.add(this);
				return l;
			}
		}

		return null;
	}
	ArrayList<Task> findCycle() {
		ArrayList<Task> seen = new ArrayList<>();
		return findCycle(seen);
	}

	void calcTimes() {
		if (this.timesCalculated)
			return;

		int firstPossibleStart = 0;

		for (Task t: this.deps) {
			t.calcTimes();
			if (t.earliestFinished > firstPossibleStart)
				firstPossibleStart = t.earliestFinished;
		}

		this.earliestStart = firstPossibleStart;
		this.earliestFinished = firstPossibleStart + this.time;
		this.timesCalculated = true;
	}

	void calcLatestStart() {
		int biggestPossibleSlack = Integer.MAX_VALUE;
		for (Task t: this.tasksWhichDepend) {
			int slack = t.earliestStart - (this.earliestStart + this.time);
			if (slack < biggestPossibleSlack)
				biggestPossibleSlack = slack;
		}

		if (biggestPossibleSlack == Integer.MAX_VALUE)
			this.slack = 0;
		else
			this.slack = biggestPossibleSlack;

		this.latestStart = this.earliestStart + this.slack;
	}

	public String identify() {
		return id+" ("+name+")";
	}
}