Монокарп хочет устроить вечеринку. У него есть $$$n$$$ друзей, и он хочет, чтобы на его вечеринке было как минимум $$$2$$$ из них.
Лучший друг $$$i$$$-го друга — это $$$p_i$$$. Все $$$p_i$$$ различны, и для каждого $$$i \in [1, n]$$$, $$$p_i \ne i$$$.
Монокарп может отправлять приглашения друзьям. $$$i$$$-й друг придет на вечеринку, если приглашение получат и друг $$$i$$$, и друг $$$p_i$$$ (обратите внимание, что друг $$$p_i$$$ не обязан прийти на вечеринку). Каждое приглашение отправляется ровно одному другу.
Например, если $$$p = [3, 1, 2, 5, 4]$$$, и Монокарп отправляет приглашения друзьям $$$[1, 2, 4, 5]$$$, то на вечеринку придут друзья $$$[2, 4, 5]$$$. Друг $$$1$$$ не придет, так как его лучший друг не получил приглашение; друг $$$3$$$ не придет, так как он не получил приглашение.
Вычислите минимальное количество приглашений, которые Монокарп должен отправить, чтобы как минимум $$$2$$$ друга пришли на вечеринку.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк:
Выведите одно целое число — минимальное количество приглашений, которые Монокарп должен отправить.
353 1 2 5 442 3 4 122 1
2 3 2
В первом наборе входных данных Монокарп может отправить приглашения друзьям $$$4$$$ и $$$5$$$. Оба придут на вечеринку, так как они лучшие друзья друг друга, и у каждого из них есть приглашение.
Во втором наборе Монокарп может отправить приглашения друзьям $$$1, 2$$$ и $$$3$$$, например. Тогда придут друзья $$$1$$$ и $$$2$$$: у друга $$$1$$$ и его лучшего друга $$$2$$$ есть приглашения, у друга $$$2$$$ и его лучшего друга $$$3$$$ есть приглашения. Друг $$$3$$$ не придет, так как его лучший друг $$$4$$$ не имеет приглашения. Невозможно отправить приглашения меньше чем $$$3$$$ друзьям таким образом, чтобы пришло хотя бы $$$2$$$.
В третьем наборе Монокарп может отправить приглашения обоим друзьям $$$1$$$ и $$$2$$$, и оба придут.
Название |
---|