Bajtysia와 Bajteusz는 Bajtocja의 거의 모든 구석을 방문한 유명한 여행가입니다. 이 땅은 $1$부터 $n$까지 번호가 매겨진 $n$개의 도시로 구성되어 있으며, 일방통행 도로망으로 연결되어 있습니다. 하지만 그들은 전통적인 여행 방식에 싫증을 느꼈습니다. 이미 갈 수 있는 곳은 모두 가보았기 때문입니다.

최근 Bajtysia는 고대 마법 유물인 '도로 등록부(Road Register)'를 손에 넣었습니다. 이 유물을 사용하면 도시 사이에 새로운 일방통행 도로를 만들 수 있습니다. 하지만 한 가지 조건이 있습니다. 등록부의 마법은 변덕스러워서, 현재 도로망을 이용해 첫 번째 도시에서 두 번째 도시로 이동할 수 없는 경우에만 도로를 만들 수 있습니다(즉, 첫 번째 도시에서 두 번째 도시로 이어지는 도로의 경로가 존재하지 않아야 합니다. 단, 두 번째 도시에서 첫 번째 도시로 가는 경로는 존재할 수도 있습니다). 이미 연결된 도시 사이에 도로를 만들려고 시도하면 실패하며 등록부가 파괴됩니다.

Bajtysia와 Bajteusz에게 이것은 아주 멋진 도전입니다! 그들은 즉시 가능한 한 많은 새로운 도로를 만들기로 결심했습니다.

안타깝게도 Bajtysia와 Bajteusz는 다음 탐험을 계획하느라 너무 바빠서 이 문제를 스스로 해결할 수 없습니다. 그들이 총 도로의 개수를 최대화할 수 있도록 어떤 도로를 순서대로 만들어야 할지 계획하는 것을 도와주세요.

입력

입력의 첫 번째 줄에는 도시의 수 $n$과 일방통행 도로의 수 $m$($1 \le n \le 1500$, $0 \le m \le n(n-1)$)이 주어집니다. 다음 $m$개의 줄에는 도로에 대한 정보가 주어집니다. 이 중 $i$번째 줄($1 \le i \le m$)에는 도시 $a_i$에서 도시 $b_i$로 가는 일방통행 도로가 있음을 나타내는 두 정수 $a_i, b_i$($1 \le a_i, b_i \le n, a_i \neq b_i$)가 주어집니다. 설명된 일방통행 도로는 중복되지 않습니다.

출력

출력의 첫 번째 줄에는 각 도로를 추가할 때마다 해당 도시 쌍 사이로 이동할 수 없는 상태여야 한다는 조건을 만족하며 만들 수 있는 최대 일방통행 도로의 개수 $k$를 출력합니다. 다음 $k$개의 줄에는 만들어야 할 도로를 순서대로 설명합니다. 이 중 $i$번째 줄($1 \le i \le k$)에는 $i$번째 도로를 만들어야 하는 두 도시 $c_i, d_i$를 나타내는 두 정수를 출력합니다. 이 도로를 만드는 시점에 이미 존재하는 도로(초기 도로 및 이전에 생성된 도로)를 사용하여 도시 $c_i$에서 도시 $d_i$로 이동할 수 없어야 합니다. 가능한 해결책이 여러 가지라면 그중 아무거나 출력해도 됩니다.

예제

예제 입력 1

7 8
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7

예제 출력 1

3
4 1
6 4
7 6

예제 입력 2

3 0

예제 출력 2

5
3 1
3 2
2 1
2 3
1 2

참고

예제 설명: 첫 번째 예제에서 처음에 존재하는 도로망은 아래와 같습니다.

도시 4에서 도시 1로 이동할 수 없으므로, 해당 도로를 추가하여 아래와 같은 도로망을 얻을 수 있습니다.

도시 6에서 도시 4로, 도시 7에서 도시 6으로 가는 도로를 추가하면 모든 도시 쌍 사이를 이동할 수 있는 도로망을 얻게 됩니다. 더 이상 추가할 수 있는 간선은 없습니다.

서브태스크

답의 첫 번째 줄만 맞춘 경우, 해당 테스트 케이스 점수의 50%를 받게 됩니다. 이 점수를 받기 위해 이후의 줄들을 출력할 필요는 없습니다.