Cerința

Considerăm un ansamblu format din n roți dințate, numerotate de la 1 la n, ca în imaginea alăturată. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.

Exemplu

gears.in

7 4
1 2
1 3
1 4
1 5
3 6
3 7

gears.out

SDDDDSS

Explicație

#include <bits/stdc++.h>


using namespace std;

ifstream cin("gears.in");
ofstream cout("gears.out");

int n , x , y , m , p , d[1001] , v[1001];
vector <int> G[1001];

void bfs(int s)
{
    queue <int> Q;
    v[s] = 1;
    d[s] = 1;
    Q.push(s);
    while(!Q.empty())
    {
        int x = Q.front();
        for(int i : G[x])
            if(!v[i])
            {
                Q.push(i);
                v[i] = 1;
                d[i] = d[x] + 1;
            }
        Q.pop();
    }
}


int main()
{
    cin >> n >> p;
    while(cin >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }

    bfs(p);

    for(int i = 1 ; i <= n ; i++)
        if(d[i] % 2 == 1) cout << "D";
        else cout << "S";
}