28397번 - 계통수 추론 스페셜 저지

계통수(phylogenetic tree)는 다양한 종 또는 개체의 유사성, 물리적 특성, 유전적 특성 등의 차이에 근거하여 유추된 진화적 관계를 보여주는 다이어그램이며, 루트 정점이 있는 트리로 표현된다.

지연이는 오랜 세월의 연구를 통해 $N$개의 종 사이 상관관계를 규명하는 가설 $M$개를 제안해 냈다. 각 종은 $1$부터 $N$까지의 서로 다른 양의 정수로 구분된다. 지연이는 연구를 검증하기 위해 $i$번 종이 정점 $i$에 대응되는 계통수를 만들어보고자 한다.

루트 정점이 있는 트리의 두 정점 $x$와 $y$에 대해, 두 정점이 같거나 정점 $x$가 정점 $y$의 부모 정점의 조상일 때 정점 $x$는 정점 $y$의 조상이다. 정점 $x$가 정점 $y$의 조상이면 정점 $y$는 정점 $x$의 후손이며 그 역도 성립한다. 두 정점의 최소공통조상은 두 정점을 후손으로 가지는 정점 중 조상의 수가 가장 많은 정점이다.

지연이가 연구를 통해 제안한 가설은 각각 $(a,b,c,d)$ 꼴로 주어진다. 각 가설은 계통수의 정점 $a$와 정점 $b$의 최소공통조상이 정점 $x$이고 정점 $c$와 정점 $d$의 최소공통조상이 정점 $y$일 때, 정점 $x$가 정점 $y$의 후손이며 정점 $x$와 정점 $y$가 다르다고 주장한다.

$N$개의 종에 대한 $M$개의 가설이 주어질 때 $i$번 종이 정점 $i$에 대응되는 계통수를 만들어보자. 모든 조건을 충족하는 계통수가 존재한다면 모든 정점의 번호가 $1$ 이상 $2N$ 이하인 계통수가 존재함을 보일 수 있다.

첫 번째 줄에 지연이가 연구한 종의 개수 $N$과 가설의 개수 $M$이 공백으로 구분되어 주어진다. $(4\leq N\leq 2\, 000;$ $1\leq M\leq 2\, 000)$

이후 $M$개의 줄에 걸쳐 각 가설을 의미하는 네 정수 $a,b,c,d$가 공백으로 구분되어 주어진다. $(1\leq a,b,c,d\leq N;$ $a\neq b;$ $c\neq d)$

모든 가설을 충족하는 계통수 $T$가 존재하지 않으면 첫째 줄에 -1을 출력한다. 그렇지 않으면, 첫째 줄에 계통수 $T$를 구성하는 정점의 개수 $N'$ $(N\leq N'\leq 2N)$을 출력한다. 이때 계통수 $T$는 정점 $1$, 정점 $2$, $\cdots$, 정점 $N'$으로 구성된다. 둘째 줄에 $N'$개의 정수 $P_1,P_2,\cdots ,P_{N'}$을 공백으로 구분하여 출력한다. 정점 $i$가 $T$의 루트 정점일 때 $P_i$는 $0$이며, 그 외에는 정점 $i$의 부모 정점의 번호이다.

가능한 계통수가 여러 가지일 경우 아무거나 하나 출력한다.