짐비의 정원에는 한 그루의 나무가 있다.
봄이 되자 나무의 끝가지마다 잎이 한 장씩 돋아났다. 여름 내내 푸르게 자란 잎들은 가을이 되자 빨간색 또는 노란색으로 물들었다. 이제 겨울을 앞두고, 짐비는 나뭇가지를 털어 잎을 모두 떨어뜨리려고 한다.
나무는 번부터 번까지 번호가 붙은 정점과 개의 간선으로 이루어진 트리이다. 밑동을 나타내는 번 정점이 루트이며, 자식이 없는 정점을 끝가지라고 한다. 각 끝가지에는 잎이 정확히 한 장 달려 있다. 이면 번 정점이 끝가지이다.
짐비는 번 정점에서 시작하여 다음 과정을 수행한다.
즉, 한 자식 정점으로 뻗은 가지의 잎을 모두 떨어뜨린 뒤에야 다음 자식 정점으로 넘어갈 수 있다. 자식들을 처리하는 순서는 각 정점에서 자유롭게 정할 수 있다.
짐비는 빨간 잎이 최대한 많이 연속해서 떨어지는 모습을 보고 싶다. 모든 잎이 한 장씩 떨어지는 순서에서, 빨간 잎이 연속해서 떨어지는 개수의 최댓값을 구해 보자.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 빨간 잎이 연속해서 떨어지는 개수의 최댓값을 출력한다.
빨간 잎이 하나도 없다면 을 출력한다.
잎이 달린 정점들을 순서로 처리할 수 있다.
이때 떨어지는 잎의 색은 차례대로 노랑, 빨강, 빨강, 노랑, 노랑, 빨강이다. 빨간 잎 두 장이 연속해서 떨어진다.
번, 번, 번 정점 아래에는 각각 빨간 잎과 노란 잎이 한 장씩 있다. 각 가지의 두 잎은 연속해서 떨어져야 하므로, 빨간 잎 세 장을 모두 연속해서 떨어뜨릴 수는 없다.
첫째 줄에 정점의 개수 과 빨간 잎의 개수 가 주어진다.
다음 개의 줄에 간선으로 연결된 두 정점의 번호가 주어진다. 번 간선은 번 정점과 번 정점을 연결한다. 이면 간선을 나타내는 줄은 주어지지 않는다.
마지막 줄에 빨간 잎이 달린 끝가지의 번호 가 주어진다. 번호는 서로 다르며, 모두 자식이 없는 정점의 번호이다. 나머지 끝가지의 잎은 노란색이다.
이면 마지막 줄은 주어지지 않는다.