모노폴리

Deni는 모노폴리 게임을 아주 좋아한다. 그런데 한 판이 너무 길다. 5시간에서 7시간이나 걸린다. 그래서 Deni는 고전적인 규칙을 바꿀 생각을 한다. 모노폴리에서 플레이어들은 보통 한 방향으로 칸에서 칸으로 이동하고, 얼마 뒤에는 시작점으로 돌아와 다시 시작하고, 이 과정을 반복한다. 새 버전에서도 이동은 칸에서 칸으로 이루어지지만, 현재 칸에서 다음으로 갈 수 있는 곳이 여러 개일 수 있다. Deni는 칸 사이의 방향 연결을 잘 정해서, 플레이어가 어떻게 이동하든(물론 규칙을 따르면서) 이미 방문한 칸으로 절대 돌아갈 수 없게 만들고 싶다. 그러면 게임 시간이 짧아진다.

그녀는 이미 새 보드를 만들기 시작했다. 칸의 개수 N을 정했고(칸에는 1부터 N까지 번호가 붙는다), M개의 연결 목록을 만들었다. 각 연결에는 방향이 있고, 자기 자신과 이어지는 연결은 없다. 칸 i가 칸 j로 이어져 있으면, 반대 방향, 즉 칸 j에서 칸 i로 가는 직접 연결은 없고, 칸 i에서 칸 j로 가는 다른 직접 연결도 없다. Deni는 새 보드가 완성됐다고 생각했지만, 문득 자신이 원하는 조건(연결을 따라 칸에서 칸으로 이동할 때 이미 방문한 칸으로 돌아갈 수 없다)이 자신의 연결 목록에서는 성립하지 않는다는 것을 알아차린다. 처음에는 직접 연결 몇 개를 없애려 했지만, 그러면 목록을 다시 써야 하고 그 목록은 아주 길 수 있다. 그래서 Deni는 일부 방향 연결의 방향을 뒤집기로 했다.

당신은 Deni와 모노폴리를 자주 한다. 그래서 그녀를 돕기 위해, 어떤 연결의 방향을 뒤집어야 조건이 성립하는지 알려 주는 프로그램을 작성하려 한다. 이 프로그램에는 함수 find_reverse가 있어야 하며, 이 함수는 심사위원의 프로그램과 함께 컴파일된다.

• 3 ≤ N ≤ 5 × 10^5
• 3 ≤ M ≤ 1.5 × 10^6