Дуб имеет \(n\) гнезд, пронумерованных целыми числами от \(1\) до \(n\). Гнездо \(i\) это дом для \(b_i\) пчел и \(w_i\) ос.
Некоторые гнезда соединены ветками. Мы называем два гнезда соседними если существует ветка, соединяющая их. Простой путь из гнезда \(x\) в \(y\) задается последовательностью \(s_0, \ldots, s_p\) различных гнезд, где \(p\) это неотрицательное целое число и \(s_0 = x\), \(s_p = y\) и \(s_{i-1}\) и \(s_{i}\) соседние для всех \(i = 1, \ldots, p\). Ветки дуба расположены так, что для любой пары гнезд \(x\) и \(y\) существует единственный простой путь из \(x\) в \(y\). По причине этого и биологи и программисты согласны, что дуб, по факту, является деревом.
Деревня это непустое множество \(V\) гнезд, такое что для всех \(x\) и \(y\) из \(V\), существует простой путь из \(x\) в \(y\), все гнезда вдоль которого также лежат в \(V\).
Множество деревень \(\cal P\) называется разбиением если каждое из \(n\) гнезд содержится в ровно одной деревне из \(\cal P\). Другими словами, никакие две деревни из \(\cal P\) не содержат одно и то же гнездо и в объединении дают все \(n\) гнезд.
На дубе проводится ежегодный конкурс красоты мисс Punyverse. Всего два участника участвуют в этом году, это некрасивая оса и красивая пчела. Победитель конкурса красоты определяется голосованием, систему которого мы сейчас опишем. Пусть \(\mathcal{P}\) это разбиение гнезд на \(m\) деревень \(V_1, \ldots, V_m\). Проводится локальные выборы в каждой деревне. Каждое насекомое в деревне голосует за свое любимое насекомое. Если в деревне окажется, что строго больше голосов отдано за некрасивую осу чем за красивую пчелу, тогда некрасивая оса объявляется победителем в этой деревне. Иначе, красивая пчела побеждает.
Известно, что пчелы всегда голосуют за пчел, то есть проголосуют за красивую пчелу в этом году и осы всегда голосуют за ос, то есть проголосуют за некрасивую осу в этом году. Все насекомые в улье участвуют в голосовании.
Мэр Waspacito, а также его заместитель Alexwasp, хотят, чтобы некрасивая оса победила. Они имеют влияние и могут выбрать разбиение дуба на ровно \(m\) деревень. Если они выберут разбиение оптимально, определите максимальное количество деревень, в которых победит некрасивая оса.
Примечание
В первом тестовом случае, нужно разделить \(n = 4\) гнезд на \(m = 3\) деревень. Мы можем так разделить, что некрасивая оса победит в \(2\) деревнях, например с помощью такого разбиения: \(\{\{1, 2\}, \{3\}, \{4\}\}\). В этом разбиении:
- Некрасивая оса побеждает в деревне \(\{1, 2\}\), получив \(181\) голосов тогда как красивая пчела получила \(170\) голосов;
- Некрасивая оса также побеждает в деревне \(\{3\}\), получив \(111\) голосов тогда как красивая пчела получила \(70\) голосов;
- Некрасивая оса проиграет в деревне \(\{4\}\), получив \(0\) голосов тогда как красивая пчела получила \(50\).
Таким образом некрасивая оса победила в \(2\) деревнях и можно показать, что это максимально возможное число.
Во втором тесте мы должны разделить \(n = 2\) гнезд на \(m = 1\) деревень. Есть только один способ это сделать: \(\{\{1, 2\}\}\). В этом разбиении некрасивая оса получит \(563\) голосов и красивая пчела также получит \(563\) голосов. Некрасивая оса побеждает, если получает строго больше голосов. Поэтому некрасивая оса не выиграет ни в какой деревне.