Huge thanks in advance to all the problem setters. Really excited for this round and the amazing problems ahead!

its means cute in persian? lol nice. nice..

What about sweetweasel who got bronze :(

nonzero

depend on tourist performance

happy birthday

unfortunately, almost every contest is held at this time, so you might be kind of screwed

EST has to get up at 4 in the morning lol

Yes, because I am also a huge fan of Kevin.

Iranian tradition is so goood.. liked it..

nope

I can't open it either. Fortunately the rest of the system seems to work. With the dashboard you can see how many people solved a given problem.

u don`t need casework for C

It may not be difficult to implement, but it requires careful analysis of the problem For the problem to have a solution: 1. The graph must not be a circle (it must be a tree) 2. If we root the tree from a leaf, all children except one must be leaves (you can check) Then you have to go and multiply your answer by the following value at each step: (count is the number of leaves) ans *= count! ans %= mod Finally multiply by 4 (horizontal and vertical symmetry) We also have an exception!!! If the graph is star-shaped (all vertices are connected to one vertex) Then the answer is 2 * (n-1)!

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

/* Besme allahe alrahman alrahim */

#define mod 1000000007

struct Node {
    char color='w';
    int h;
    int par;
    bool barg=false;
    vector<int> hamsa;
};
vector<Node> nodes;
int n;
bool mishe=true;
bool canzarb=true;
long long ans=1;

long long fac(int x) {
    long long ani=1;
    for(int i=1; i<=x; i++) {
        ani*= 1ll*i;
        ani%= mod;
    }
    return ani;
}

void dfs(int x) {
    nodes[x].color='r';

    if(nodes[x].hamsa.size()==1) {
        nodes[x].barg=true;
    } if(nodes[x].hamsa.size()==n-1) {
        canzarb=false;
    }

    for(int i: nodes[x].hamsa) {
        if(nodes[i].color=='w') {
            nodes[i].h=nodes[x].h+1;
            nodes[i].par=x;
            dfs(i);
        } else {
            if(i!=nodes[x].par) {
                mishe=false;
            }
        }
    }
}

void dfs2(int x) {
    nodes[x].color='r';
    int all=(int)nodes[x].hamsa.size();
    int count=0;

    for(int i: nodes[x].hamsa) {
        if(nodes[i].barg) {
            count++;
        }
        if(nodes[i].color=='w') {
            dfs2(i);
        }
    }

    if(all-1-count>1) {
        mishe=false;
    }
    ans*= fac(count);
    ans%= mod;
}


void solve() {
    int m;
    cin>>n>>m;

    for(int i=0; i<n; i++) {
        nodes.push_back(Node());
    }
    for(int i=0; i<m; i++) {
        int a,b; cin>>a>>b; a--; b--;
        nodes[a].hamsa.push_back(b);
        nodes[b].hamsa.push_back(a);
    }

    if(n==2) {
        cout<<2<<endl; return;
    }

    nodes[0].h=0;
    dfs(0);

    if(mishe==false) {
        cout<<0<<endl; return;
    }
    for(int i=0; i<n; i++) {
        nodes[i].color='w';
    }

    for(int i=0; i<n; i++) {
        if(nodes[i].barg) {
            dfs2(i);
            break;
        }
    }
    if(mishe==false) {
        cout<<0<<endl; return;
    }

    if(canzarb) {
        cout<<(4ll*ans)%mod<<endl;
    } else {
        cout<<(2ll*fac(n-1))%mod<<endl;
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin>>t;
    while(t--) {
        solve();
        nodes.clear();
        mishe=true;
        canzarb=true;
        ans=1;
    }

    return 0;
}

First, note that if the graph isn't a tree (or a forest, but statement says it's connected), the answer is $$$0$$$, because there's no way to build a cycle of bridges without a self-intersection or a bridge connecting two houses on the same side. Then, note that assuming the answer is $$$ \gt 0$$$, in the tree, every vertex can have at most $$$2$$$ neighbors which aren't leaves, otherwise there is a non-leaf neighbor fully cut off by remaining bridges from this vertex, a contradiction. Thus, the non-leaf vertices of the tree form a path (assuming a non-leaf vertex exists, but otherwise $$$n=2$$$ and the answer is clearly $$$2$$$)). Then, note that there are either $$$2$$$ or $$$4$$$ "distinct" ways to create the path, depending on whether it's size is at least $$$2$$$ (choices are first riverbank and "direction"), and then for each vertex on the path neighboring $$$d$$$ leaves, they all have to be between the neighbors on the path in any order, so we get $$$d!$$$ options for each. Just multiply everything and we're done.

I was trying this, but only passed the given test case

1. First assign 0/1 colours to all nodes; two nodes with an edge should have opposite colours. if not possible -> return 0
2. Second, start with a node having degree 1, traverse all nodes, and only one of these nodes should have a degree > 1 to prevent the crossing

If both of the above conditions are satisfied, then only we can have an arrangement

For the total number of arrangements

1. For every node having degree > 1, find how many nodes are connected with degree 1, because we can permute them. Let's say it is x1, x2, x3 and so on — then total arrangements would be x1! * x2! * x3! * ...
2. Then we can flip up and down so multiply by 2 ( this is only applicable when there are at least 2 nodes with degree > 1)
3. Then we can flip right, left, so again multiply by 2

Not sure what is wrong with this approach. Can someone please point out the mistake

probably

bro did not read my comments

I can only access it using my phone.

You are right! I couldn't find a solution better than O(nk) then I just search on chatgpt on find number of n-element arrays of sum y such that each element is at most k, and it gives me the closed solution using exclusion-inclusion. Then, I ask to do the same on number of n-element arrays of sum at most y and each element at most k, and it gives me a very clean solution computable in O(k) time (by using some combinatoric magic) which gives us a O(nlogn) solution! Too bad, I only read your comment after the contest!

istg same

literally got me brainstorming with pen and paper for an hour. When I finally got AC, I was so happy.

gainFromPair can larger than 1e9

awesome man. I only thought about sorting a. somehow i did not think about sorting b and checking. Good for me that by the time i got to "my solution" time ran out xD

your code did not compile on judge compiler,

if it compiled successfully on your machine then it might be setting difference.

You can take some (i, j) pair over and over again so its basically solve for k = 1 everytime. Then u just need to find (i, j) pair that adds least amount to original answer and just take that all the time. Furthermore if u have a[i], b[i] and a[j], b[j] then this pair only adds extra if max(a[i], b[i]) < min(a[j], b[j]) or vice versa and it adds 2*(min-max). So we sort pairs {min(a[i], b[i]), max(a[i], b[i])} check if there exists any adjacent pairs such that min < max(basically add 0) and if none exist take the minimum of min-max of adj pairs.

First thing first, only 1 round matters, because Ali can keep choosing the same i and j and only one time Bahamin can gain points. Now, If you have i and j, such that max(ai, bi) >= min(aj, bj), then there will no score gain from this pair and Ali can choose this pair, otherwise try to minimise gain, which you can see here: 332903480

C is doing good, thank you for you concern.

this can help https://mirror.codeforces.com/blog/entry/145242?#comment-1300336

can you please share you easy idea for B

Yes. It is about $$$\exp(n/2)$$$. Now we realize that we should change this problem into counting...