레이팅 미적용농부 존은 농장 곳곳에 일방통행 소 길을 설치했다. 농장은 1..N번으로 번호가 매겨진 N개의 목초지로 이루어져 있으며, 각 일방통행 길은 두 목초지를 연결한다 (X에서 Y로 가는 길은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없다).
베시는 항상 목초지 1에서 출발해 여러 목초지를 차례로 방문한 뒤 하루가 끝나면 목초지 1로 돌아온다. 베시는 경로에서 방문하는 서로 다른 목초지의 수를 최대화하려 한다 (같은 목초지를 여러 번 방문해도 한 번으로만 센다).
베시는 규칙을 어기고 최대 한 개의 길을 역방향으로 지나간다면 풀을 얼마나 더 먹을 수 있을지 궁금하다. 목초지 1에서 출발하고 끝나는 경로에서, 최대 한 개의 길을 역방향으로 지나갈 수 있을 때 방문할 수 있는 서로 다른 목초지 수의 최댓값을 계산하시오. 같은 길을 역방향으로 두 번 지나갈 수는 없다.
첫째 줄에 목초지의 수 N과 일방통행 길의 수 M이 주어진다 (1 <= N, M <= 100,000).
다음 M개의 줄 각각에는 서로 다른 두 목초지 번호 X와 Y가 주어지며, X에서 Y로 가는 소 길을 나타낸다. 같은 소 길이 두 번 이상 주어지는 일은 없다.
목초지 1에서 출발하고 끝나며 최대 한 개의 길을 역방향으로 지나가는 경로에서 베시가 방문할 수 있는 서로 다른 목초지 수의 최댓값을 한 줄에 출력한다.
grass.in · 출력을 쓸 파일 grass.out7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 76Output details: Bessie can visit 1, 2, 4, 7, 2, 5, 3, 1 by traveling backwards on the path between 5 and 3.