| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 78 | 20 | 17 | 26.562% |
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 $c$ $(1 \leq c \leq 100)$ and the number of roads $r$ $(c-1 \leq r \leq 10^4)$. On the next $r$ lines, three integers $a,ドル $b$ and $w$ are given, with $a$ and $b$ the endpoints of a road and $w$ $(1 \leq w \leq 10^4)$ the length of that road.
One line with two integers $p$ and $q$. With $p$ the number of roads with prime length and $q$ the number of roads with non-prime length.
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
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