문제

자율주행 기술은 현대 컴퓨팅의 여러 최첨단 기술에 의존하지만, 이것이 가능하게 하려면 자동차에서 할 수 없는 복잡한 계산과 실시간 도로 정보 확인 등을 중앙 서버에서 빠르고 신속하게 처리할 수 있어야 한다. 이를 위해서 흔히 사용되는 방법은 요청(request)을 처리하는 많은 워커 노드(worker node)들을 두고, 로드 밸런서(load balancer)가 이들 워커 노드에 트래픽을 적절히 분산시키는 것이다.

현재 총 개의 서버가 있다. 이 문제에서 서버는 로드 밸런서 또는 워커 노드를 의미하며, 각각의 서버가 동시에 로드 밸런서이면서 워커 노드일 수는 없다. ()번째 서버가 트래픽을 분산시키는 서버들은 중복을 포함하여 총 개 있다. 이면 번째 서버는 워커 노드로, 요청을 직접적으로 처리한다. 이라면, 번째 서버는 로드 밸런서로, 아래와 같은 라운드-로빈 (Round-Robin) 방식으로 트래픽을 분산한다.

• 각각의 로드 밸런서에는 정수형 변수 가 있다. 처음에 이다.
• 로드 밸런서로 요청이 하나 들어오면, 번 서버로 트래픽을 전달하고, 의 값을 로 바꾼다.

1번 서버는 루트 로드 밸런서로, 웹 서버로의 모든 요청은 루트 로드 밸런서로만 들어온다.

주어진 트래픽 분산 규칙은 효율적인 분산이 가능하도록 아래 두 조건을 만족한다.

• 트래픽이 같은 로드 밸런서를 여러 번 거치지 않도록, 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
• 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.

총 개의 요청이 들어왔다고 할 때, 각 서버로 들어오는 요청의 개수가 몇 개인지를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 두 정수 과 가 공백 하나씩을 사이로 두고 주어진다.

다음 개의 줄에 , , , , 가 공백 하나씩을 사이로 두고 주어진다.

• 이다.
• 모든 , 에 대해, 이다.
• 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
• 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.

출력

개의 정수를 공백 하나씩을 사이로 두고 출력한다. ()번째 정수는, 번 서버가 받는 요청의 개수이다.

서브태스크

노트

예제 1번 로드밸런서의 구조는 아래와 같다.

6개의 요청이 아래와 같이 전달된다.