int f(int ind , int n , vector&a , vector&b) {

vector<int>adj[n + 1];

int m = a.size();

for (int i = 0 ; i < m ; i++) {

    if (i == ind)continue;

    adj[a[i]].push_back(b[i]);

    adj[b[i]].push_back(a[i]);

}

vector<int>dist(n + 1 , 1e9);

dist[1] = 0;

queue<int> q;

q.push(1);

while (!q.empty()) {

    int u = q.front();

    q.pop();

    for (auto v : adj[u]) {

       if (dist[v] > 1 + dist[u]) {

         dist[v] = 1 + dist[u];

         q.push(v);

       }

    }

}

return dist[n] == 1e9 ? -1 : dist[n];

}

vector townTravel(int n , vector&a , vector& b) {

int m = a.size();

vector<int> ans;

for (int i = 0 ; i < m ; i++) {

    int num = f(i , n , a , b);

    ans.push_back(num);

}

return ans;

}

void solve() { int n ; cin >> n;

string s ; cin >> s;

vector<int> check(n);

for (int i = 0 ; i < n ; i++) check[i] = (s[i] == '1');

vector<int>a(n); input(a);

vector<int>indegree(n);

for (int i = 0 ; i < n ; i++)

{

    indegree[--a[i]]++;

}

queue<int> q;

vector<int> ans;

for (int i = 0 ; i < n ; i++)

{

    if (indegree[i] == 0)q.push(i);

}

while (!q.empty())

{

    int u = q.front(); q.pop();

    if (check[u])

    {

       ans.push_back(u);

       check[u] = !check[u];

       check[a[u]] = !check[a[u]];

    }

    indegree[a[u]]--;

    if (indegree[a[u]] == 0)q.push(a[u]);

}

for (int i = 0 ; i < n ; i++)

{
    if (indegree[i])

    {

       int j = i;

       int length = 0 , track = 0 , res = 0;


       while (indegree[j])

       {

         if (check[j]) track ^= 1;

         res += track;

         indegree[j] = 0;

         length++;

         j = a[j];

       }

       if (track == 1)

       {

         cout << -1 << endl;

         return;

       }

       for (int k = 0  ; k < length ; k++)

       {

         if (check[j]) track ^= 1;

         if (track == (res < length- res))

         {
          ans.push_back(j);
         }
         j = a[j];
       }
    }
}
cout << ans.size() << endl;
for (auto a : ans) cout << a + 1 << " ";
cout << endl;

}

Firstly, let's find some diameter of the tree. Let a and b be the endpoints of this diameter (and first two vertices of the answer). You can prove yourself why it is always good to take the diameter and why any diameter can be taken in the answer. Then there are two cases: the length of the diameter is n−1 or the length of the diameter is less than n−1. In the first case, you can take any other vertex as the third vertex of the answer c, it will not affect the answer anyway. Otherwise, we can run multi-source bfs from all vertices of the diameter and take the farthest vertex as the third vertex of the answer. It is always true because we can take any diameter and the farthest vertex will increase the answer as much as possible.