최악의 기자

당신은 스포츠 기사를 담당하는 신문사 기자입니다.

어제까지 $n$개의 축구팀이 참가한 리그전(round-robin, 모든 팀이 서로 한 번씩 맞붙는 리그)이 열렸습니다. 대회 운영 위원회는 경기 결과와 규정에 따라 각 팀에게 1위부터 $n$위까지 서로 다른 순위를 매겼습니다. 당신에게는 일부 경기의 승패와 함께 다음 정보가 전달되었습니다.

• 정보 1: 무승부인 경기는 없었습니다.
• 정보 2: 모든 팀의 순위는 서로 다릅니다.
• 정보 3: $1 \le a < b \le n$인 모든 $a$, $b$에 대해, $a$위 팀과 $b$위 팀의 경기에서는 반드시 $a$위 팀이 이겼습니다. (즉, 순위가 더 높은 팀이 순위가 더 낮은 팀을 항상 이깁니다.)

일부 경기의 승패와 정보 1~3을 바탕으로, 전달된 정보에 모순되지 않는 순위표를 하나 복원하고, 그 순위표 외에 정보에 모순되지 않는 다른 순위표가 존재하는지도 판정하세요.

순위표란 1위부터 $n$위까지 팀을 차례대로 나열한 것을 말합니다.

정보에 모순되지 않는 순위표가 여러 개일 수 있으므로, 그중 사전순으로 가장 앞서는 순위표를 출력하세요. (1위부터 $n$위까지 나열한 팀 번호의 수열을 사전순으로 비교하여 가장 작은 것을 고릅니다.)

첫째 줄에 축구팀의 수 $n$이 주어집니다. 각 팀에는 1부터 $n$까지의 번호가 붙어 있습니다.

둘째 줄에 알려진 경기 승패의 개수 $m$이 주어집니다.

이어지는 $m$개의 줄에는 각각 공백으로 구분된 두 정수 $i$, $j$가 주어지며, 이는 번호 $i$인 팀이 번호 $j$인 팀을 이겼음을 나타냅니다.

$n$, $m$은 $1 \le n \le 5000$, $1 \le m \le 100000$을 만족합니다.

출력은 $n + 1$개의 줄로 이루어집니다.

첫째 줄부터 $n$째 줄까지에는 정보에 모순되지 않는 순위표를 출력합니다. $i$째 줄 ($1 \le i \le n$)에는 $i$위 팀의 번호를 출력하세요. 조건을 만족하는 순위표가 여러 개라면 사전순으로 가장 앞서는 것을 출력합니다.

$n + 1$째 줄에는 출력한 순위표 외에 정보에 모순되지 않는 다른 순위표가 존재하는지를 나타내는 정수를 출력합니다. 존재하지 않으면(순위표가 유일하면) 0을, 존재하면 1을 출력하세요.