당신은 JOI 신문사의 기자이며, 스포츠 기사를 담당하고 있다.

어제까지 크로아티아에서는 $n$개의 축구팀에 의한 풀리그전이 열렸다. 대회 실행위원회는 경기 결과와 규정에 근거하여 각 팀에 $1$위부터 $n$위까지의 순위를 매긴 것 같다. 당신에게는 일부 경기의 승패와 함께 다음 정보가 전달되었다.

• 정보 $1$: 무승부인 경기는 없었다.
• 정보 $2$: 모든 팀에 서로 다른 순위가 매겨졌다.
• 정보 $3$: 모든 $1 \le a < b \le n$에 대하여, $a$위인 팀과 $b$위인 팀의 경기에서 반드시 $a$위인 팀이 승리했다.

당신은 기사를 작성하기 위해 일부 경기의 승패와 전달받은 정보 $1$~$3$을 바탕으로 순위표를 추측하기로 했다.

입력으로 일부 경기의 승패가 주어졌을 때, 전달받은 정보에 부합하는 순위표를 $1$개 출력하는 프로그램을 작성하라. 또한 출력한 순위표 이외에 전달받은 정보에 부합하는 순위표가 존재하는지 여부도 판정하라.

여기서 순위표란 $1$위부터 $n$위까지의 순서대로 팀을 나열한 것을 말한다.

예

예 1 (정보에 부합하는 순위표가 $1$개뿐인 경우)

팀의 수가 $4$이고, 각 팀에 $1$부터 $4$까지의 번호가 붙어 있으며, 승패가 다음 표로 주어졌다고 하자.

$i$행 $j$열이 $\circ$일 때는 번호 $i$인 팀과 번호 $j$인 팀의 경기에서 번호 $i$인 팀이 승리했음을 의미한다. 또한 $\times$일 때는 번호 $j$인 팀이 승리했음을 의미한다. $?$는 승패가 주어지지 않았음을 의미한다.

이때 전달받은 정보에 부합하는 순위표는 다음 $1$개뿐이다.

• $1$위: 번호 $3$인 팀
• $2$위: 번호 $4$인 팀
• $3$위: 번호 $1$인 팀
• $4$위: 번호 $2$인 팀

예 2 (정보에 부합하는 순위표가 여러 개 존재하는 경우)

팀의 수가 $3$이고, 각 팀에 $1$부터 $3$까지의 번호가 붙어 있으며, 승패가 다음 표로 주어졌다고 하자.

이때 전달받은 정보에 부합하는 순위표는 다음 $2$개이다.

• $1$위: 번호 $2$인 팀, $2$위: 번호 $1$인 팀, $3$위: 번호 $3$인 팀
• $1$위: 번호 $2$인 팀, $2$위: 번호 $3$인 팀, $3$위: 번호 $1$인 팀

입력

$1$번째 줄에는 축구팀의 수 $n$이 적혀 있다. 각 팀에는 $1$부터 $n$까지의 번호가 붙어 있다.

$2$번째 줄에는 주어진 경기 승패의 개수 $m$이 적혀 있다.

$3$번째 줄부터 $m + 2$번째 줄까지는 경기의 승패를 나타낸다. 각 줄은 공백으로 구분된 $2$개의 정수 $i, j$를 포함하며, 번호 $i$인 팀이 번호 $j$인 팀에게 승리했음을 나타낸다.

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

채점에 사용되는 테스트 데이터 중 $30\%$는 $1 \le n \le 7$, $1 \le m \le 15$를 만족한다. 또한 $60\%$는 $1 \le n \le 100$, $1 \le m \le 2000$을 만족한다.

출력

출력은 $n + 1$줄로 이루어진다.

$1$번째 줄부터 $n$번째 줄까지의 $n$줄에는 전달받은 정보에 부합하는 순위표를 출력하라. $i$번째 줄 ($1 \le i \le n$)에 $i$위인 팀의 번호를 출력하라.

$n + 1$번째 줄에는 출력한 순위표 이외에 전달받은 정보에 부합하는 순위표가 존재하는지 여부를 나타내는 정수를 출력하라. 만약 존재하지 않으면 $0$을, 존재하는 경우에는 $1$을 출력하라.

입출력 예

입출력 예 1의 입력

예 $1$에 대응하는 입출력은 다음과 같다.

4
5
1 2
3 1
3 2
3 4
4 1

입출력 예 1의 출력

3
4
1
2
0

입출력 예 2의 입력

예 $2$에 대응하는 입력 데이터는 다음과 같다.

3
2
2 1
2 3

이 입력 데이터에 대하여 다음 $2$가지 출력 데이터를 생각할 수 있다. 어느 쪽을 출력해도 좋다.

입출력 예 2의 출력

2
1
3
1

2
3
1
1