UVa Q10187

//UVa Q10187
#include <bits/stdc++.h>
using namespace std;

struct stat{
    int city, T, blood;
    bool operator>(const stat &x)const{return blood > x.blood;}
};
vector<int> route[105], start[105], ended[105];
map<string, int> mp;
int vis[105][12];

int main(){
    int t, n, a, b, cnt = 0;
    string s1, s2;
    cin >> t;
    while(t--){
        cin >> n;
        int k = 0;
        mp.clear();
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < 100; ++i){
            route[i].clear();
            start[i].clear();
            ended[i].clear();
        }
        for(int i = 0; i < n; ++i){
            cin >> s1 >> s2 >> a >> b;
            if((6 <= a && a < 18) || (6 < (a+b)%24 && (a+b)%24 <= 18) || b > 12)continue;
            if(mp.find(s1) == mp.end())mp[s1] = k++;
            if(mp.find(s2) == mp.end())mp[s2] = k++;
            route[mp[s1]].emplace_back(mp[s2]);
            a = (a >= 18)? a-18 : a+6;
            start[mp[s1]].emplace_back(a);
            ended[mp[s1]].emplace_back(a+b);
            //cout << s1 << ' ' << s2 << ' ' << a << ' ' << b << endl;
        }
        cin >> s1 >> s2;
        if(mp.find(s1) == mp.end())mp[s1] = k++;
        if(mp.find(s2) == mp.end())mp[s2] = k++;
        stat one = {.city = mp[s1], .T = 0, .blood = 0};
        priority_queue<stat, deque<stat>, greater<stat> > pq;
        pq.push(one);
        int ans = -1;
        while(!pq.empty()){
            stat tmd = pq.top();
            pq.pop();
            //cout << tmd.city << ' ' << tmd.T << ' ' << tmd.blood << endl;
            if(!vis[tmd.city][tmd.T])vis[tmd.city][tmd.T] = 1;
            else continue;
            if(tmd.city == mp[s2]){
                ans = tmd.blood;
                break;
            }
            for(unsigned i = 0; i < route[tmd.city].size(); ++i){
                stat nxt = {.city = route[tmd.city][i],
                            .T = ended[tmd.city][i],
                            .blood = (tmd.T <= start[tmd.city][i])? tmd.blood : tmd.blood+1};
                //cout << ' ' << nxt.city << ' ' << nxt.T << ' ' << nxt.blood << endl;
                if(!vis[nxt.city][nxt.T])pq.push(nxt);
            }
        }
        cout << "Test Case " << ++cnt << ".\n";
        if(ans == -1)cout << "There is no route Vladimir can take.\n";
        else cout << "Vladimir needs " << ans << " litre(s) of blood.\n";
    }
    return 0;
}