Factory

//package hiit;

import java.util.*;

public class F {
	
	static HashSet<Integer>[] downLine;
	static HashSet<Integer>[] upLine;
	static int[] children;
	static int[] parents;
	static PriorityQueue<Job> q;

	public static void main(String[] args) {
		int time = 0;
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		children = new int[n+1];
		parents = new int[n+1];
		downLine = new HashSet[n+1];
		upLine = new HashSet[n+1];
		for (int i=1; i<=n; i++) {
			downLine[i] = new HashSet();
			upLine[i] = new HashSet();
		}
		for (int i=1; i<=m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			children[a]++;
			parents[b]++;
			downLine[a].add(b);
			upLine[b].add(a);
		}
		
		HashSet<Integer> notDone = new HashSet<>();
		for (int i=1; i<=n; i++) {
			notDone.add(i);
		}
		while (!notDone.isEmpty()) {
			time++;
			HashSet<Integer> unlockableSingles = new HashSet<>();
			HashSet<Integer> secondBestChoiceUnlockableParents = null;
			HashSet<Integer> bestChoiceUnlockableParents = null;
			int bestVal = 0;
			for (Integer i : notDone) {
				HashSet<Integer> immediatelyUnlockableParents = new HashSet<>();
				if (downLine[i].size() == 0 && upLine[i].size() == 0) unlockableSingles.add(i);
				for (Integer dad : upLine[i]) {
					if (parents[dad] > 0) continue;
					immediatelyUnlockableParents.add(dad);
					if (immediatelyUnlockableParents.size() == 2) break;
				}
				int val = immediatelyUnlockableParents.size();
				if (val > bestVal) {
					bestVal = val;
					secondBestChoiceUnlockableParents = bestChoiceUnlockableParents;
					bestChoiceUnlockableParents = immediatelyUnlockableParents;
				}
				if (val >= 2) {
					break;
				}
			}
			int counter = 0;
			if (bestChoiceUnlockableParents != null) {
				for (Integer node : bestChoiceUnlockableParents) {
					unlock(node);
					notDone.remove(node);
					counter++;
				}
			}
			if (counter < 2 && secondBestChoiceUnlockableParents != null) {
				for (Integer node : secondBestChoiceUnlockableParents) {
					if (bestChoiceUnlockableParents.contains(node)) continue;
					unlock(node);
					notDone.remove(node);
					counter++;
				}
			}
			if (counter < 2 && unlockableSingles.size() > 0) {
				for (Integer node : unlockableSingles) {
					unlock(node);
					notDone.remove(node);
					counter++;
					if (counter == 2) break;
				}
			}
		}
		
		
		/*
		q = new PriorityQueue<>();
		for (int i=1; i<=n; i++) {
			if (parents[i] == 0) {
				q.add(new Job(i, children[i]));
			}
		}
		
		
		while (!q.isEmpty()) {
			time++;
			Job wait = q.poll();
			if (!q.isEmpty()) work(q.poll());
			work(wait);
		}*/
		
		System.out.println(time);
	}
	
	static void unlock(Integer node) {
		//System.out.println("Unlocing " + node);
		for (Integer child : downLine[node]) {
			parents[child]--;
			upLine[child].remove(node);
		}
	}
	
	static void work(Job job) {
		for (Integer child : downLine[job.node]) {
			parents[child]--;
			if (parents[child] == 0) {
				q.add(new Job(child, children[child]));
			}
		}
	}
	
	

}

class Job implements Comparable<Job> {
	int node;
	int children;
	
	public Job(int node, int children) {
		this.node = node;
		this.children = children;
	}

	@Override
	public int compareTo(Job o) {
		if (this.children > o.children) return -1;
		if (this.children < o.children) return 1;
		return 0;
	}
	
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: ACCEPTED