시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

어떤 k개의 나라와 n-k개의 무역을 중개해주는 포트 있다. 나라들이 서로 무역을 하는데 이런 나라들이 서로 물자를 교환하기 위해서는 무역을 중개해주는 포트를 거쳐야 한다. 즉, 만약에 a라는 나라에서 b라는 나라로 물자를 보내려면 c라는 포트를 거쳐서 a->c->b라는 경로를 통해서 가야 한다는 것이다.

우리가 할 일은 다음과 같다. 어떤 나라와 무역을 중개해주는 곳, 그리고 무역을 중개해주는 곳 끼리 물량을 주고받는 양이 주어진다. 그랬을 때, 시작도시와 도착 도시가 주어져 있을 때, 시작도시에서 도착 도시로 보내는 양의 최대값, 최소값이 얼마인지 구하는 것이다. 단, a라는 나라에서 b라는 포트로 보낸 물량이 b에서 a로 다시 돌아가는 경우는 없다고 하자.

예를 들어 위와 같은 그래프가 있다고 하자. (1, 2, 4, 5, 7, 9) 는 나라, (3, 6, 8)은 포트이다. 여기서 1번 도시에서 4번 도시로 갈 수 있는 최대 물량은 3, 최소물량은 1이다. (1번 도시에서 4번 도시로 가는 경로는 1,6,3,8,4 인데 1에서 6으로 4만큼의 물량을 보내면 4중 1은 꼭 2로 가야한다. 그리고 남은 3이 3으로 가고 이 3이 경로를 따라 4번 나라로 갈 수 있다. 그리고 1에서 6으로 보내는 4중 1은 반드시 4

입력

첫 줄에 나라의 수와 포트의 수의 합인 N이 주어진다. 그리고 두 번째 줄부터 N번째 줄까지 무역양의 정보가 주어진다. 각 줄에는 네 개의 정수 a,b,c1,c2 가 공백을 사이에 두고 주어지는데, 이는 a에서 b로 c1, b에서 a로 c2만큼의

출력

첫째 줄에 시작 국가에서 도착 국가로 가는 물량의 최소값과 최대값을 차례로 출력하시오.

예제 입력

9
1 6 4 1
2 6 2 1
6 3 4 0
7 3 1 1
9 3 1 1
3 8 6 2
8 4 4 1
8 5 2 1
1 4

예제 출력

1 3

힌트