dd

// div1 easy (cgy4ever's solution)
public class DoubleOrOneEasy {
    public int minimalSteps(int a, int b, int newA, int newB)
    {
        int INF = 1100000000;
        int ret = INF;
        for(int i = 0; i < 30; i++)
        {
            long d = newA - 1L * a * (1<<i);
            long d2 = newB - 1L * b * (1<<i);
            if(d != d2) continue;
            if(d < 0) continue;
            int cnt = i;
            for(int j = i; j >= 0; j--)
            {
                int amount = (int)d / (1<<j);
                cnt += amount;
                d -= (1<<j) * amount;
            }
            ret = Math.min(ret, cnt);
        }
        if(ret == INF) return -1;
        return  ret;
    }
}

// div1 med (Arterm's solution)
#include <bits/stdc++.h>

using namespace std;

const int M = 104;
typedef long long ll;

vector<int> g[M];
int n;
long mx;
ll d[M][M];
ll temp[M];
bool used[M];

void merge(ll *d, ll *h) {
  fill(temp, temp + M, 0);

  for (int i = 0; i <= mx; ++i) {
    for (int j = 1; i + j <= mx; ++j)
      temp[max(i, j)] += d[i] * h[j - 1];
    for (int j = 2; i + j <= mx; ++j)
      temp[max(i, j)] += d[i] * h[j - 2];
  }

  copy(temp, temp + M, d);
}

void dfs(int v) {
  used[v] = true;
  fill(d[v], d[v] + M, 0);
  d[v][0] = 1;

  for (int to : g[v])
    if (!used[to]) {
      dfs(to);
      merge(d[v], d[to]);
    }
}

class DiameterOfRandomTree {
public:
  double getExpectation(vector<int> a, vector<int> b) {
    n = a.size() + 1;
    for (int i = 0; i < n - 1; ++i) {
      g[a[i]].push_back(b[i]);
      g[b[i]].push_back(a[i]);
    }

    ll ans = 0;
    ll prev = 0;
    for (mx = 0; mx < M; ++mx) {
      fill(used, used + M, 0);
      dfs(0);
      ll bon = 0;
      for (int i = 0; i <= mx; ++i)
        bon += d[0][i];
      ans += (bon - prev) * mx;
      prev = bon;
    }

    return 1.0 * ans / (1ll << (n - 1));
  }
};

# div1 hard (lg5293's solution)
class GameOnGraph():
    def findSolution(self, graph, p):
        n = len(p)
        conn = [[graph[i][j] == 'Y' for j in range(n)] for i in range(n)]

        # first find a hamiltonian cycle,
        seen = [False] * n
        cycle = []
        for j in range(n):
            for k in range(n):
                if conn[0][j] and conn[j][k] and conn[k][0]:
                    cycle = [0,j,k]
                    seen[0] = seen[j] = seen[k] = True
                    break
            if len(cycle) > 0: break

        def growCycle(prev):
            din = []
            dout = []
            for next in range(n):
                if seen[next]: continue
                for idx in range(len(prev)):
                    nid = (idx+1)%len(prev)
                    if conn[prev[idx]][next] and conn[next][prev[nid]]:
                        seen[next] = True
                        return prev[nid:] + prev[:nid] + [next]

                if conn[next][prev[0]]:
                    din.append(next)
                else:
                    dout.append(next)

            for x in din:
                for y in dout:
                    if conn[y][x]:
                        seen[x] = seen[y] = True
                        return prev + [y,x]

        while len(cycle) != n:
            cycle = growCycle(cycle)

        ret = []
        curp = list(p)
        def move(a,b):
            ret.append(a)
            curp[a],curp[b] = curp[b],curp[a]

        # then bubble sort.
        comp = [cycle.index(i) for i in range(n)]
        goal = range(n)
        pos = cycle.index(0)
        while curp != goal:
            a,b,c = cycle[pos%n], cycle[(pos+1)%n], cycle[(pos+2)%n]
            if comp[curp[b]] == n-1 or comp[curp[b]] < comp[curp[c]]:
                move(a,b)
                pos += 1
            else:
                if conn[a][c]:
                    move(a,c)
                    pos += 2
                else:
                    move(a,b)
                    move(b,c)
                    move(c,a)
            pos %= n
        return ret[::-1]