비행기, 기차, 그러나 자동차는 없다

영업사원으로 일하는 것은 힘든 일이다. Per는 그러한 영업사원이며, 외국에 있는 모든 도시를 정확히 한 번씩 방문하는 효율적인 방법을 찾고 싶어 한다.

Per는 효율성을 독특하게 정의하는데, 비행기를 타는 것을 몹시 싫어하기 때문이다. 더 나쁘게도 그는 자동차를 절대 이용하지 않는다. Per가 가장 좋아하는 교통수단은 기차다. 그는 가능한 한 오래 기차를 탈 것이다.

이 나라의 철도 시스템은 매우 독특하고 매우 제한적이다. 모든 철도 노선은 단방향이며, 어떤 도시에서 기차를 타고 나가면 그 도시로 돌아오는 철도 노선의 순서는 존재하지 않는다. 이는 나라가 더 비싼 비행기로 돈을 벌려고 하기 때문이다. 이 나라에서는 모든 도시에 공항이 정확히 하나씩 있어서, 어떤 도시에서든 다른 어떤 도시로든 비행기로 이동할 수 있다.

Per는 필요한 최소 비행 횟수만 알고 싶은 것이 아니다. 그는 또한 가장 적은 비행으로 어떤 여행을 할 때 어느 도시에서 공항을 방문할 수 있는지도 알고 싶어 한다. Per는 공항 식당을 좋아하기에, 자신이 가장 좋아하는 식당을 방문할 수 있도록 경로를 선택하고자 어떤 식당을 방문할 수 있는지 알고 싶어 한다. 그는 도시로 비행기를 타고 들어오거나 나갈 때 공항을 방문할 수 있다. Per는 어느 도시에서든 시작할 수 있다.

네 개의 도시가 있는 이 나라를 생각해 보자. 화살표는 단방향 철도 노선을 나타낸다.

Per가 택할 수 있는 여행은 여러 가지가 있지만, 그는 적어도 한 번은 비행기를 타야 한다. 다음은 가장 적은 비행을 하는 몇 가지 (모든 것은 아닌) 가능한 경로이며, →는 기차 이동, ⇒는 비행을 나타낸다.

• 1 → 2 → 4 ⇒ 3
• 2 → 4 ⇒ 1 → 3
• 1 → 3 → 4 ⇒ 2

이 예에서 모든 공항은 적어도 하나의 경로에서 방문된다. Per는 원하는 어떤 공항 식당이든 방문할 수 있도록 경로를 선택할 수 있다.

각 테스트 케이스는 공백으로 구분된 두 정수 n (1 ≤ n ≤ 105)과 m (0 ≤ m ≤ 105)이 있는 줄로 시작한다. n은 도시의 수이고 m은 철도 노선의 수이다. 도시는 1..n으로 번호가 매겨진다.

다음 m개의 줄 각각은 공백으로 구분된 두 정수 a와 b (1 ≤ a, b ≤ n, a ≠ b)를 포함하며, 이는 도시 a에서 도시 b로 가는 철도 노선이 있음을 나타낸다(반대 방향은 없다). 모든 철도 노선은 서로 다르다.

정확히 두 줄을 출력한다.

첫째 줄에는 Per가 모든 도시를 방문하기 위해 타야 하는 최소 비행 횟수를 나타내는 정수 하나를 출력한다.

둘째 줄에는 그가 방문할 수 있는 공항이 있는 도시들의 목록을 공백으로 구분하여 출력한다. 최소 비행 횟수를 가진 경로 중 어느 하나에서든 공항을 방문할 수 있다면, 그 도시를 나열해야 한다. 이 번호들을 오름차순으로 출력한다. 방문할 공항이 없다면 빈 줄을 출력한다.