Composius' Wrath

시간 제한1초메모리 제한2048 MB

요약
가중치가 있는 연결 무향 그래프에서 간선 길이가 소수인 간선의 수가 최대가 되는 신장 트리를 찾아, 소수 길이 간선 수와 그렇지 않은 간선 수를 출력한다.
난이도

보통10점 중 7점

유형
최소 신장 트리, 유니온 파인드, 수학, 그리디
정답자
아직 제출이 없습니다

문제

After many years of praising their god Primos, the very wealthy land of Primozia had a large number of cities that were connected by many roads, enabling traders to travel from every city to every other city in very little time. This caused the god Composius to be very displeased, because he does not like to see such wealth in a country that idolizes prime numbers. Therefore he cast his wrath upon the land of Primozia and destructed all their trade routes by the force of an incredible tsunami.

After hearing about this, the first priority of the pharaoh of Primozia was to rebuild the network of roads such that all trading can continue. However, in order to connect every city with every other city as soon as possible, the pharaoh orders to rebuild the road network with as few roads as possible, such that a path exists from every city to every other city. Additionally, he wants to rebuild as many roads with prime lengths as possible, because prime numbers are sacred in the land of Primozia.

입력

On the first line two integers, the number of cities cc (1≤c≤100)(1 \leq c \leq 100) and the number of roads rr (c−1≤r≤104)(c-1 \leq r \leq 10^4). On the next rr lines, three integers aa, bb and ww are given, with aa and bb the endpoints of a road and ww (1≤w≤104)(1 \leq w \leq 10^4) the length of that road.

출력

One line with two integers pp and qq. With pp the number of roads with prime length and qq the number of roads with non-prime length.

예제2

  1. 예제 1

    입력
    7 9
1 2 1
2 3 7
2 4 5
2 6 5
3 4 9
4 5 6
4 6 11
5 7 8
5 6 13
    예상 출력
    4 2

  2. 예제 2

    입력
    7 12
1 2 5
1 6 64
1 7 12
2 3 11
2 7 21
3 4 17
3 7 32
4 5 83
4 7 18
5 6 113
5 7 19
6 7 7
    예상 출력
    6 0