#include <iostream>
#include <cstdio>
#include <ctime>
#include <vector>
#include <cstring>
#include <random>
#include <map>
#include <utility>
#include <algorithm>
#include <fstream>
#include <cstdlib>

using namespace std;
//1 _WIN32
#ifdef _WIN32
#define WINDOWS_ENVIRONMENT 1
//1
#else
//2 WIN32
#ifdef WIN32
#define WINDOWS_ENVIRONMENT 1
//2
#else
//3 _WIN64
#ifdef _WIN64
#define WINDOWS_ENVIRONMENT 1
//3
#else
//4 WIN64
#ifdef WIN64
#define WINDOWS_ENVIRONMENT 1
//4
#else
//5 WINDOWS
#ifdef WINDOWS
#define WINDOWS_ENVIRONMENT 1
//5
#else
//6 __linux__
#ifdef __linux__
#define LINUX_ENVIRONMENT 1
//6
#else
//7 Unknown
#define UNKNOWN_ENVIRONMENT 1
//6
#endif
//5
#endif
//4
#endif
//3
#endif
//2
#endif
//1
#endif

#ifdef WINDOWS_ENVIRONMENT
inline void REMOVE_FILE(const char *__FILE_NAME__)
{
    char __cmd__[1024];
    sprintf(__cmd__, "rd %s ", __FILE_NAME__);
    system(__cmd__);
}
#else
#ifdef LINUX_ENVIRONMENT
#define REMOVE_FILE(__FILE_NAME__) system("rm -f " __FILE_NAME__)
#endif
#endif
namespace maker
{

class gragh_t
{
    struct edge
    {
        int from, to, dis, next;
        edge(int f, int t, int d, int n)
        {
            from = f, to = t, dis = d, next = n;
        }
    };
    vector<int> *head;
    vector<gragh_t::edge> *Edge;
    int N, E;
    inline int HEAD(int at)
	{
		return head->operator[](at);
	}
	inline gragh_t::edge EDGE(int at)
	{
		return Edge->operator[](at);
	}
    void add_edge(int from, int to, int dis)
    {
        Edge->push_back((edge){from, to, dis, head->operator[](from)});
        head->operator[](from) = Edge->size();
    }
    gragh_t friend operator|(gragh_t &a, gragh_t &b)
    {
        gragh_t ans(max(a.N, b.N), max(a.E, b.E));
        for (int i = 1; i <= b.N; i++)
        {
            for (int j = b.head->operator[](i); ~j; j = b.Edge->operator[](j).next)
            {
                gragh_t::edge now = b.Edge->operator[](j);
                a.add_edge(i, j, now.dis);
            }
        }
        return ans;
    }
    inline void friend operator|=(gragh_t &a, gragh_t &b)
    {
        return a = a | b;
    }
    gragh_t(int nodenum, int edgenum)
    {
        N = nodenum, E = edgenum;
        head = new vector<int>(nodenum + 5, -1);
        gragh_t::edge base(0, 0, 0, -1);
        Edge = new vector<edge>(edgenum + 5, base);
    }
};

// typedef long long int lli;
// typedef pair<int, int> prii;
#define lli long long int
#define prii pair<int, int>
// #define default_mod 19260817

struct IO_module
{
private:
    // input/output file name
    char ofile[1011];
    char ifile[1011];

    // flow of output to the ifile/ofile
    ofstream fout;
    ifstream fin;

public:
    /* quick scanner of an integer.
     * warn: it will read all the charactors that is not digits.
     * you can just us it like scan an integer.
     */
    template <typename Tp>
    inline Tp NextInt()
    {
        Tp num = 0;
        char ch = getchar();
        bool flag = false;
        while (!isdigit(ch))
            flag |= ch == '-', ch = getchar();
        while (isdigit(ch))
            num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
        return flag ? -num : num;
    }

    // to reset the output file name to __o_file_name__[]
    inline void set_ofile(const char *__o_file_name__)
    {
        sprintf(ofile, "%s", __o_file_name__);
        fout.close();
        fout.open(__o_file_name__, ios::out);
    }

    // to reset the input file name to __i_file_name__[]
    inline void set_ifile(const char *__i_file_name__)
    {
        sprintf(ifile, "%s", __i_file_name__);
        fin.close();
        fin.open(__i_file_name__, ios::in);
    }

    IO_module()
    {
        sprintf(ofile, "%s", "datas.out");
        //ofstream Fout("datas.out");
        //memcpy(&fout, &Fout, sizeof(ofstream));//fout = Fout;
        fout.open("datas.out", ios::out);
        fin.open("maker.in", ios::in);
    }

    IO_module(const char *__user_ofile__)
    {
        sprintf(ofile, "%s", __user_ofile__);
        fout.open(__user_ofile__, ios::out);
        fin.open("maker.in", ios::in);
    }

    IO_module(const char *__user_ofile__, const char *__user_ifile__)
    {
        sprintf(ofile, "%s", __user_ofile__);
        sprintf(ifile, "%s", __user_ifile__);
        fout.open(__user_ofile__, ios::out);
        fin.open(__user_ifile__, ios::in);
    }
};

// static defines here -->
// IO module here
/* old version refer to "char ofile[1001];" 
     * and refer to this
     * flow of output to the ofile
     * FILE *fout;
     */
// new module from version 0.5.1 has seperated

// the gragh which has been saved.
map<prii, bool> Saved;
map<prii, bool> Saving;

// integer rand limit
// 19260817 for its origin
lli Integer_rand_limit = 19260817;

/* integer rand limit of edges' weight
     * 19260817 for its origin
     * 114514 for not to give a limit
     */
lli weight_limit = 19260817;

/*
     * the static integer limit of string maker 
     * about the ammount of the strings contains from the dictionary
     * (the dictionary refer to vector<string> &__dict__)
     */
int __ammount_limit__ = 500;

mt19937 RandInt(time(NULL));

// to get the version on your console.
inline void Version()
{
    puts("Jelly Data Maker version 1.7.3.");
    puts("Written by lcez-oi in Jinan.");
    puts("All rights reserved.");
}

inline string data_file_name(const char *__prefix__, const int __data_id__, const char *__shuffix__)
{
    char __NUM__[128];
    sprintf(__NUM__, "%d", __data_id__);
    string res = __prefix__;
    res = res + __NUM__;
    res = res + __shuffix__;
    return res;
}

// out of gragh here -->
// to set the integers' rand limit
inline void Int_range(lli __limit__)
{
    Integer_rand_limit = __limit__;
}

// to set limits of the integers as the weight of edges
inline void set_weight_limit(lli edge_rand_limit)
{
    weight_limit = edge_rand_limit;
}

// to get the integer of random
inline lli Rand(lli __limits__)
{
    return RandInt() % __limits__ + 1;
}

//to make an array if n integers!
//Iterator __left__ for a begin iterator, which can be a *int etc
//but __left__ should reconstructed iterator ++
//if it would be something interesting
template <class __Iterators__>
inline void Integer_array(int n, __Iterators__ __left__)
{
    for (int i = 1; i <= n; i++)
    {
        //fprintf(fout, "%lld ", Rand(Integer_rand_limit));
        *__left__ = Rand(Integer_rand_limit);
        __left__++;
    }
}

inline lli range_rand(int __l_limit__, int __r_limit__)
{
    return __l_limit__ + Rand(__r_limit__ - __l_limit__);
}

// to make some integer ranges
//Iterator __left__ for a begin iterator, which can be a *int etc
//but __left__ should reconstructed iterator ++
//if it would be something interesting
//cautions the type should fit pair<int,int>
template <class __Iterators__>
inline void Ranges_maker(int n, __Iterators__ __left__, int __l_limit__ = 1, int __r_limit__ = 19260817)
{
    for (int i = 1; i <= n; i++)
    {
        int l = range_rand(__l_limit__, __r_limit__);
        *__left__ = make_pair(l, range_rand(l, __r_limit__));
        __left__++;
    }
}

// gragh makers here -->
/* to make a tree as a undirected gragh
     * includes n nodes
     * return with gragh_t type that can use more times
     */
inline gragh_t tree_maker(int __node__)
{
	gragh_t res(__node__, __node__ - 1);
	for (int i = 2; i <= __node__; i++)
	{
		res.add_edge(i, Rand(i - 1), Rand(weight_limit));
	}
	return res;
}

/* this is a Directed gragh maker that promise
     * there is no circle made by it
     * it would be returned with gragh_t type
     */
inline gragh_t DAG_maker(int __node__, int __edge__)
{
	gragh_t res(__node__, __edge__);
	for (int i = 2; i < __node__ && i <= __edge__; i++)
	{
		int to = i + Rand(__node__ - i);
		res.add_edge(i, to, Rand(weight_limit));
	}
	__edge__ -= __node__ - 1;
	for (int i = 1; i <= __edge__; i++)
	{
		int from = Rand(__node__);
		int to = Rand(__node__ - from);
		res.add_edge(from, to, Rand(weight_limit));
	}
	return res;
}

/* to make a undirected gragh
     * include n nodes and m edges
     * can promise it would all be connected
     * returned with gragh_t type.
     */
inline gragh_t ugragh_maker(int __node__, int __edge__)
{
	gragh_t res(__node__, __egde__);
	Saving.clear();
	for (int i = 2; i <= __node__ && i <= __edge__ + 1; i++)
	{
		int from = i, to = Rand(i - 1);
		res.add_edge(from, to, Rand(weight_limit)));
		Saving[make_pair(from, to)] = true;
	}
	__edge__ -= __node__ - 1;
	for (int i = 1; i <= __edge__; i++)
	{
		int from = i, to = i;
		while (from == to || Saving[make_pair(from, to)] == true)
			from = Rand(__node__), to = Rand(__node__);
		res.add_edge(from, to, weight_limit);
		Saving[make_pair(from, to)] = true;
	}
}

/* warn: this function does not to repare all the nodes connects together
     * this can hack some wrone codes like tarjan on some gragh
     * totally random gragh
     * add no chains and flowers!
     * return with gragh_t type
     */
inline gragh_t Random_grah(int __node__, int __edge__)
{
	gragh_t res(__node__, __edge__);
	for (int i = 1; i <= __edge++; i++)
	{
		res.add_edge(Rand(__node__), Rand(__node__), Rand(weight_limit));
	}
}

/* hack gragh maker
     * flower for flower gragh
     * chain for chain gragh
     * these can combine and make a haker gragh
     * warn: flower add chain can not be more than 1
     *  or hacked yourself(haha)
     * return with gragh_t type.
     */
inline gragh_t Haker_gragh(int __node__, int __edge__, double flower = 0.00, double chain = 0.00)
{
	gragh_t res(__node__, __edge__);
	int chain_node = __node__ * chain + 1;
	for (int i = 1; i < chain_node; i++)
	{
		res.add_edge(i, i + 1, Rand(weight_limit));
	}
	int flower_node = __node__ * flower;
	for (int i = 1; i <= flower_node; i++)
	{
		res.add_edge(chain_node, chain_node + i, Rand(weight_limit));
	}
	for (int i = chain_node + flower_node + 1; i <= __node__; i++)
	{
		int to = Rand(__node__);
		res.add_edge(i, to, Rand(weight_limit));
	}
	__edge__ -= __node__;
	for (int i = 1; i <= __edge__; i++) 
	{
		res.add_edge(Rand(__node__), Rand(__node__), Rand(weight_limit));
	}
	return res;
}

inline string Makestr(vector<string> &__dict__)
{
    int __ammount = Rand(__ammount_limit__);
    string res = "";
    for (int i = 1; i <= __ammount; i++)
    {
        int __now = Rand(__dict__.size()) - 1;
        res = res + __dict__[__now];
    }
    return res;
}

}; // namespace maker
// ending
#ifdef LINUX_ENVIRONMENT
#undef LINUX_ENVIRONMENT
#endif

#ifdef WINDOWS_ENVIRONMENT
#undef WINDOWS_ENVIRONMENT
#endif

#ifdef UNKNOWN_ENVIRONMENT
#undef UNKNOWN_ENVIRONMENT
#endif