21562번 - 우물 유적 발굴하기 서브태스크스페셜 저지

과거 폴리매스 문명의 사람들은 $N$개의 우물을 사용한 것으로 알려져 있습니다. 당신은 우물의 위치를 모두 알아내었습니다. 힘겹게 땅을 파는 대신, 당신은 빠른 속도로 유적을 발굴하기 위해 $N$개의 위치에 적당한 세기의 폭탄을 설치하였습니다.

당신은 $N$개의 폭탄을 $M$개의 전선을 이용해 연결했습니다. (각 전선은 두 폭탄을 서로 연결합니다.) 폭탄들이 무질서하게 터지는 것을 방지하기 위해, 각 전선별로 방향을 정해 불꽃이 한 방향으로만 번질 수 있게 하였습니다.

각 전선이 연결한 폭탄의 번호는 결정했지만, 전선의 방향은 결정하지 않았습니다. 전선의 방향을 정했을 때, 폭탄의 위험도는 $S= \max_{1 \le i \le N} (|A_i -B_i |)$로 계산됩니다. (단, $A_i$는 번 폭탄으로 들어오는 전선의 수, $B_i$는 번 폭탄에서 나가는 전선의 수)

위험도를 최소로 하는 전선의 방향을 찾아봅시다.

첫 줄에는 폭탄의 수 $N$과 전선의 수 $M$이 주어집니다.

둘째 줄부터 $M+1$번 줄까지, 각 전선이 연결하는 폭탄의 번호 $u_i$, $v_i$가 주어집니다.

첫 줄에는 가능한 최소의 위험도를 출력합니다.

둘째 줄부터 $M+1$번 줄까지, 각 전선의 방향을 $a_i b_i$의 형태로 출력합니다. $a_i$, $b_i$는 각각 $u_i$, $v_i$ 중 하나이며, $i$번 전선의 방향이 $a_i$번 폭탄에서 $b_i$번 폭탄으로 향하는 형태라는 의미입니다.

• $2 \le N, M \le 10^6$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• 중복 간선이 존재할 수 있습니다.