내부 정보

Ian은 최고의 대학 순위를 발표하는 평가 기관에서 일한다. Irene은 곧 발표될 순위를 소재로 특종 기사를 쓰려는 기자다.

Irene은 몇 가지 사회공학 수법을 써서 (자세한 이야기는 넘어가자) Ian에게서 내부 정보를 얻어냈다.

Irene이 받은 것은 대학 번호 세 개로 이루어진 조 $(a_i, b_i, c_i)$ 여러 개다. 각 조는 이번 순위에서 대학 $b_i$가 대학 $a_i$와 $c_i$ 사이에 온다는 뜻이다. 즉 $a_i$가 $b_i$보다 앞이고 $b_i$가 $c_i$보다 앞이거나, 그 반대다. Ian이 알려준 조는 모두 실제 순위와 어긋나지 않는다. 실제 순위는 받은 조를 전부 만족한다.

기사 초안을 쓰기 시작하려면 Irene에게는 실제 순위에 어느 정도 가까운 안이 필요하다. 받은 조 가운데 절반 이상을 만족하는 순위 안을 찾아라. 그런 안은 여러 개이므로, 출력 절에 적힌 절차가 만드는 안을 출력한다.

첫 줄에 순위를 매기는 대학의 수 $n$과 Ian이 Irene에게 알려준 조의 개수 $m$이 주어진다 ($3 \le n \le 100000$, $1 \le m \le 100000$).

다음 $m$개의 줄에는 각각 한 조를 이루는 서로 다른 세 정수 $a_i$, $b_i$, $c_i$가 주어진다 ($1 \le a_i, b_i, c_i \le n$). $m$개의 조를 모두 만족하는 순위가 적어도 하나 존재한다.

1위부터 마지막 순위까지 대학 번호를 공백 하나로 구분해 한 줄에 출력한다.

조의 절반 이상을 만족하는 안은 여러 개이므로, 다음 절차가 만드는 안을 그대로 출력한다.

1단계, 제거 순서. 처음에는 모든 조가 살아 있다. 조 $(a, b, c)$에서 $b$를 가운데 대학, $a$와 $c$를 끝 대학이라고 한다. 살아 있는 어떤 조에서도 가운데 대학이 아닌 대학을 자유로운 대학이라고 한다. 다음을 $n$번 반복한다. 아직 남아 있는 대학 가운데 자유로우면서 번호가 가장 작은 대학을 제거한다. 제거되는 순서대로 $1$번부터 $n$번까지 제거 순번을 매긴다. 대학을 제거하면 그 대학을 끝 대학으로 가지면서 살아 있던 조는 모두 죽는다. 입력 조건 덕분에 매 단계에 자유로운 대학이 존재한다.

2단계, 배치. 제거 순번의 역순으로, 순번 $n$부터 순번 $1$까지 대학을 놓는다. 순번이 $n$인 대학 하나가 시작 수열이다. 순번이 $i$인 대학 $u$는 지금까지 만든 수열의 맨 앞이나 맨 뒤에 놓는다. 세 대학의 제거 순번이 모두 $i$ 이상인 조만 본다. 그런 조에서 $u$는 끝 대학이다. 그 조의 가운데 대학을 $w$, 다른 끝 대학을 $v$라고 하자. $u$를 맨 앞에 놓으면 현재 수열에서 $w$가 $v$보다 앞에 있을 때 그 조가 만족되고, 맨 뒤에 놓으면 $v$가 $w$보다 앞에 있을 때 만족된다. 두 선택이 각각 만족시키는 조의 개수를 세어 더 많은 쪽을 고른다. 두 개수가 같으면 맨 앞에 놓는다.

이렇게 만든 안은 항상 $m/2$개 이상의 조를 만족한다.

실제 순위에서 가장 앞에 오는 대학은 어떤 조에서도 가운데 대학이 아니다. 아직 남아 있는 대학만 모아 놓고 보아도 마찬가지이므로 1단계는 도중에 막히지 않는다.

2단계에서 각 조는 세 대학 가운데 제거 순번이 가장 작은 대학을 놓는 단계에 한 번만 판정되고, 그 대학은 그 조의 끝 대학이다. 맨 앞과 맨 뒤 두 선택 가운데 하나는 그 조를 반드시 만족시키므로, 더 많은 쪽을 고르면 그 단계에서 판정되는 조의 절반 이상이 만족된다. 모든 단계를 더하면 $m/2$개 이상이 된다.