import java.util.ArrayList; import java.util.Scanner; public class TopologicalOrdersWithOnePermutation { final ArrayList> edgesFrom = new ArrayList<>(); final int[] degreeTo; final int size; final int[] answer; public TopologicalOrdersWithOnePermutation(int size) { //O(n) degreeTo = new int[size]; answer = new int[size]; for (int i = 0; i < size; ++i) { edgesFrom.add(new ArrayList<>()); } this.size = size; } public void addEdge(int from, int to) { //O(1) edgesFrom.get(from).add(to); ++degreeTo[to]; } final ArrayList myStack = new ArrayList<>(); public void createAnswer() { //O(n+m) int pos = 0; int swapPlace = -1; for (int i = 0; i < size; ++i) if (degreeTo[i] == 0) myStack.add(i); while(pos 1) { int x = myStack.remove(myStack.size()-1); int y = myStack.remove(myStack.size()-1); removeVertice(x); removeVertice(y); swapPlace = pos; answer[pos++] = x; answer[pos++] = y; continue; } int x = myStack.remove(myStack.size()-1); removeVertice(x); answer[pos++] = x; } if (swapPlace == -1) { System.out.println("one order"); for (int i = 0; i < size; ++i) System.out.print(answer[i] + " "); System.out.println(); } else { System.out.println("first order"); for (int i = 0; i < size; ++i) System.out.print(answer[i] + " "); System.out.println(); int c = answer[swapPlace]; answer[swapPlace] = answer[swapPlace + 1]; answer[swapPlace + 1] = c; System.out.println("second order"); for (int i = 0; i < size; ++i) System.out.print(answer[i] + " "); System.out.println(); } } private void removeVertice(int from) { // O(m) at all calls for (int to : edgesFrom.get(from)) { if (--degreeTo[to] == 0) //One run for each edge myStack.add(to); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); TopologicalOrdersWithOnePermutation orders= new TopologicalOrdersWithOnePermutation(n); int m = scanner.nextInt(); for(int i = 0; i