If I try little hard I can solve all problems in beginner contest, Your rating is high from mine. So it's easy to you.

I think you should participate in regular round, because beginner rounds are easier than div2.

Look at the path from 1 to n. First they will color whole path ( half one color half other). Than erase path you will get forest ( several trees ) . In each tree you will have one color and that whole tree will be colored on that way. So just count amount of nodes in "black root" trees and "white root" trees and see what is bigger.

I really hate interactive problems, I came up with solution very fast, but I didn't get AC :(

Is the last task some bitmask + max flow min cost algorithm ?

Root the tree at vertex 1, now in optimal game snuke goes up some vertices up and paints the whole subtree white. So, just check the vertices the snuke can go and take the maximum subtree.

I used a BFS maintaining 2 queues (black and white) and a distance array maintaining layers from nodes 1 and n. if a node from black has color black (let's call it t1), the distance of all it's adjacent nodes is d(t1)+1. if d(t1)+1 <= d(adjacent node) i will color it black and add it to queue. Similar thing can be done with white queue but one difference: add to white only if d(t2)+1 < d(adjacent node).

I solved by this algorithm.

1. Calculate dist(1, 1), dist(1, 2), ..., dist(1, N) and dist(N, 1), dist(N, 2), ..., dist(N, N).
2. Define two integer a, b. Initially these two are 0.
3. For each i: if dist(1, i) ≥ dist(N, i) a++, otherwise b++.

4. a means the number of vertex which can get Fennec, and b means the number of vertex which can get Snuke.
5. So if a > b, Fennec wins. Otherwise, Snuke wins.

This algorithm is correct because there is no more than one vertex which is dist(1, i) = dist(N, i).

My code is here. Sorry for my poor English.

What I did was

First maintain two array level1 and level2

Bfs from 1 and store all the values of level of all the nodes in level1

Bfs from N and store all the values of level of all the nodes in level2

Then

    for(i=1;i<=n;i++)
    {
       if(level1[i]<=level2[i])
         ans1++;
       else
         ans2++;
    }
    if(ans1>ans2)
    {
       cout<<"Fennec"<<endl;
       return 0;
    }
    cout<<"Snuke"<<endl;

Consider some vertex is painted in black at any stage of the game. Consider many components you will get when you remove current black vertex. One of that components will initially contain white vertices. White will never paint a vertex in any other component during the rest of the game. So black will paint them when the time comes in any case.

So an optimal strategy for both players will be to paint next vertex on the shortest path from vertices 1 to n. In that way, they will potentially increase the number of vertices to paint in future for themselves.

When the path is painted, you can simulate the process to see who will win. Or you can say that 1 is a root, calculate the size of the subtree for every vertex, compare the number of vertices in the subtree of the highest vertex the black player can get to with the remaining number of vertices in the whole tree.

There is no need to find path from 1 to N or to compute any distances; one queue for bfs is enough. First vertex in queue is 1, it's colored black; second vertex is N, it's colored white; problem is solved with usual bfs — in one step just color all adjusting uncolored vertices the same color current vertex has, and add those to queue. And then compare sizes of two components (if black > white Fennec wins, otherwise wins Snuke).

1. Calculate the number of digits.
   

2. Use binary search to get number. Since to be always n > N, the question number n should be multiple by 10. (This means if the number of digits of N is 2, the number of digit of n should be 3.

The code is here. Sorry for my poor English.

Um_nik uwi vintage_Vlad_Makeev ACRush izban

Please decribe your solution.

Hope this intuitive thing helps (see the editorial for details and formal proof). Let S be the set of vertices that are already "determined", and u be the last vertex on the "determined" path. Do bitmask DP over S and u (f[S][u] is the maximum sum of edge weights under that state, every time we take another u and another set to add into S), and try to prove it works in rather than 4ⁿ stuff.