Nagham loves graphs, so she came up with this idea at 12a.m. But sadly, she didn't know how to solve it. Luckily for her, Ahmad, although he is a bully, saw Marble on that day and was happy, so he decided to be a goody guy and solve it for her.
Marble The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) – the number of test cases.
The first line of each test contains $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$) ($$$1 \leq m \leq 5 \cdot 10^5$$$).
The next $$$m$$$ lines of each test contain integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) – meaning there is a directed edge from $$$u$$$ to $$$v$$$.
It's guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, output the minimum number of edges to make the graph connected.
14 51 22 33 11 43 4
1
Noorhan's birthday is just around the corner, and the excitement is building up! She's been chatting non-stop with her friends Manar and Nagham, dropping hints left and right about how many gifts she'd love to receive this year. The magic number she's been dreaming about is $$$n$$$ gifts.
Manar and Nagham have cooked up a fantastic plan. Instead of just giving her $$$n$$$ gifts, they're going to surprise her with $$$a$$$ gifts, where $$$a$$$ is the closest prime number to $$$n$$$. Help Manar and Nagham decide how many gifts they're getting Noorhan.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ – the number of test cases.
The following $$$t$$$ lines each contain an integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$.
For each test case, print one integer $$$a$$$, if there are multiple answers print the smaller one.
71234567
2 2 3 3 5 5 7
Iyad has a cat called Thlooj, and many of the cats in his neighborhood look like him, so on his birthday we decided we want to DNA a bunch of cats and see how many are related to him.
Thlooj and his brother M3m3 They tested $$$n$$$ cats, and each cat's DNA was represented by an integer $$$a_i$$$. We say a cat is related to Thlooj if they have any mutual ones in their binary representation, more specifically if $$$a_i$$$ $$$\&$$$ $$$D \gt 0$$$ where $$$D$$$ is Thlooj's DNA.
How many cats are related to Thlooj?
Note that $$$\&$$$ is the bitwise AND operator.
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of testcases.
The first line of each case contains two integers $$$n$$$ and $$$D$$$ $$$(1 \leq n \leq 2\cdot10^5; 1 \leq D \leq 10^9)$$$ – the number of cats they tested and Thlooj's DNA.
The second line of each case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print one integer, the number of cats related to Thlooj.
24 121 6 8 53 111 24 66
3 3
Manar is planning to open a coffee shop on her upcoming birthday. She wants to have a unique menu, but she's been extremely busy with all the preparations, so she has asked her friend for help. Her friend suggested that she could have drinks where the name is a palindrome formed by concatenating two words from a given array of strings. Manar liked this idea so much, so she's doing it!
Given an array of strings, find the number of distinct pairs of words $$$(s_i, s_j)$$$ such that $$$(i \neq j)$$$ and $$$s_i + s_j$$$ is a palindrome, where $$$(a + b)$$$ is the concatenation of string $$$a$$$ and string $$$b$$$.
A palindrome is a word, number, phrase, or other sequence of characters that reads the same backward as forward, such as "bananab" and "racecar".
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the length of the array $$$s$$$.
The next line of each test case contains $$$n$$$ strings $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \leq |s| \leq 4\cdot10^5)$$$ consisting of lowercase English letters, where $$$|s|$$$ denotes the length of the string $$$s$$$.
It's guaranteed that the sum of |s| over all test cases is not greater than $$$4\cdot10^5$$$.
For each test case, output a single integer — the number of distinct pairs of words where their concatenation is a palindrome.
34rak ka akar ak3abba abab aba4abc bac cba acb
4 1 2
Ahmad gave Rama the most basic birthday gift, an array $$$a$$$ of $$$n$$$ integers on a piece of paper. Unfortunately, Rama's new cat ripped it apart.
Bagheera Luckily, she remembers an array $$$b$$$ of $$$n$$$ integers such that $$$b_i = gcd(a_1, a_2, \ldots, a_i)$$$, now she wants you to construct an array $$$a$$$ that satisfies the array $$$b$$$.
Ahmad is considerate and loves cats, so he will accept any valid array $$$a$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 2\cdot10^5)$$$ – the number of integers in $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 10^9)$$$ – the array she remembers.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, if there's no valid array that satisfies $$$b$$$ print -1, otherwise print $$$n$$$ integers the array $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$. If there are multiple solutions print any.
3416 8 2 2430 15 5 143 4 2 1
16 24 10 2 30 15 25 13 -1
Osama is the biggest flower of all flowers, so on his birthday, Ahmad will gift him an endless amount of flowers <3.
Ahmad gave him $$$n$$$ bouquets of flowers. Each bouquet has some types of flowers in it, and there exists an infinite amount of each type of flowers.
Osama has a garden of length $$$m$$$, so he needs to fill it with $$$m$$$ flowers. He will fill it in the following way:
- He will first choose a bouquet of flowers (he can't change it after selecting it);
- Then he will select each of the $$$m$$$ flowers from this bouquet.
What is the number of distinct gardens he can make using the above strategy? Since the answer is huge, you have to print it modulo $$$10^9 + 7$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 5)$$$ – the number of test cases.
The first line of each case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 19;\space 1 \leq m \leq 10^9)$$$.
The next $$$n$$$ lines start with an integer $$$k$$$ $$$(1 \leq k \leq 60)$$$, then follow $$$k$$$ distinct integers $$$a_1, a_2, \ldots, a_k$$$ $$$(1 \leq a_i \leq 60)$$$.
For each test case, print an integer, the number of distinct gardens Osama can make modulo $$$10^9 + 7$$$.
22 22 2 32 1 23 43 1 2 33 3 4 53 4 5 6
7 226
The different gardens he can make in the first case are: $$$[\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}, \{2, 3\}, \{3, 2\}, \{3, 3\}]$$$
Ahmad, being the bully he is, decided to gift Nagham this problem on her birthday (smh).
He gave her $$$n$$$ nodes and $$$m$$$ weighted edges, the starting node $$$s$$$, and the ending node $$$e$$$, and asked her to get the maximum possible value of a valid route, where the value of the route is the bitwise AND of weights on it.
You, being the good person you are, decided to help Nagham solve this problem. Will you be able to help her?
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) – the number of test cases.
The first line of each test case contains four integers $$$n,m,s,e$$$ ($$$1 \leq s,e \leq 10^5$$$), ($$$2 \leq n \leq 10^5$$$), ($$$1 \leq m \leq 3\cdot10^5$$$).
The next $$$m$$$ lines contain $$$3$$$ numbers, the two nodes ($$$1\leq a,b \leq 10^5$$$) and the weight on the edge that connects them ($$$1 \leq w \lt 2^{60}$$$).
For each test case, output the answer Ahmad is looking for.
34 4 1 31 4 81 2 124 3 402 3 163 4 1 31 2 322 3 321 2 642 3 83 3 2 31 2 41 3 81 3 12
8 32 4
Abdulrahman has OCD so he is so careful with how clean and neat his codes are, so naturally he likes implementation and data structure problem, so Ahmad decided to give him one. Please don't disappoint him with your code for this data structures problem.
You're given two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$. You're also given an integer $$$k$$$, the value of any sequence $$$(1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n)$$$ is $$$\sum_{j=1}^{k}{a_{i_j}} \space - \max\limits_{1 \leq j \leq k}b_{i_j}$$$.
What's the maximum value of any sequence of length $$$k$$$?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
For each test case, the first line contains two integers $$$n$$$ $$$k$$$ $$$(1 \leq k \leq n \leq 2\cdot 10^5)$$$.
The next $$$n$$$ lines each contains two integers $$$a_i$$$ $$$b_i$$$ $$$(1 \leq a_i \leq 10^9; -10^{15} \leq b_i \leq 10^{15})$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print one integer, the maximum value of any sequence of length k.
33 13 25 64 13 23 25 64 13 33 25 64 1
3 5 6
13 21 41 41 4
-2
Zain has a very cute cat, called Khokha, which he keeps showing Ahmad pictures of; so Ahmad decided he will gift him and his cat this problem.
Khokha Khokha likes jumping around like any other cat, she specifically can jump no longer than $$$k$$$ tiles from where she is at now, meaning if she is at tile $$$i$$$ then she could jump to any tile $$$j$$$ $$$(i \lt j \leq n)$$$ such that $$$j - i \leq k$$$.
There are $$$n$$$ aligned tiles, and Khokha starts at tile $$$0$$$. In how many ways can she reach tile number $$$n$$$?
The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The next $$$t$$$ lines each contain two integers $$$n$$$ and $$$k$$$ $$$(1 \leq k \leq n \leq 10^6)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases is not greater than $$$2\cdot10^6$$$.
For each test case, print one integer, the number of ways Khokha can reach tile $$$n$$$ modulo $$$10^9 + 7$$$.
52 12 23 13 23 3
1 2 1 3 4
Hamza holds the Mansaf of his people very highly, so on his birthday, Ahmad decided he will give him a bunch of Mansaf dishes to rate.
If Hamza was to taste some set of dishes with yumminess $$$d_1, d_2, \ldots, d_k$$$, the value of this set is $$$\min\limits_{1 \leq i \leq k}d_i$$$.
Ahmad has $$$n$$$ options of dishes, each dish was from the restaurant $$$a_i$$$ and with a yumminess of $$$d_i$$$. Ahmad can only choose to buy all the dishes from only one restaurant, what is the biggest value he can provide Hamza?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
For each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 2\cdot 10^5)$$$.
The next $$$n$$$ lines each contains two integers $$$a_i$$$ $$$d_i$$$ $$$(1 \leq a_i, d_i \leq 10^9)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5\cdot10^5$$$.
Print a single integer, the maximum value he can provide For Hamza, while only having the choice of the restaurant he buys from.
2410 24 510 74 641 1050 10123 7650 74
5 76
In the first test case, if he selects the restaurant number $$$10$$$ he will get a value of $$$2$$$, but if he selects the restaurant number $$$4$$$ he will get a value of $$$5$$$, so the answer is $$$5$$$.
Ka3bool is a very smart cat, he loves programming as much as his owner Manar does, he's also known for being a cp weapon. One day, Ka3bool challenged Manar's friend with a problem that goes as follows: "meow meow meow, meow meoow.. meowww".
The friend did not understand anything of what that silly cat said, so she asked Manar to translate it for her, and she was happy to do so.
Ka3bool Let $$$S$$$ be a set of distinct integers, and let $$$f(S)$$$ be the number of non-intersecting intervals of integers in this set. For example, if $$$S = \{1, 2, 4, 5, 6, 8\}$$$, then $$$f(S) = 3$$$, since the non-intersecting intervals are $$$[(1, 2), (4, 6), (8)]$$$.
The set is empty at first, and you have to make $$$q$$$ changes of the following form:
- + $$$x$$$, add an integer $$$x$$$ to the set.
- - $$$x$$$, delete an integer $$$x$$$ from the set. It's guaranteed that $$$x$$$ is already in the set.
After each change, you have to tell Ka3bool the value of $$$f(S)$$$.
The first line of the input contains one integer $$$q (1 \leq q \leq 10^6)$$$ — the number of changes.
Then $$$q$$$ lines follow. The $$$i$$$-th line contains a character $$$c$$$ and an integer $$$x$$$ where ($$$c \in$$$ {+, -}) and $$$(0 \leq x \leq 10^{18})$$$.
After each change, output a single integer $$$f(S)$$$ — the number of non-intersecting intervals.
8+ 0+ 6+ 1- 0+ 3+ 4+ 5- 5
1 2 2 2 3 3 2 3
Monther always struggles with precision errors. To help him, Ahmad gave him a bunch of pairs and asked him the following.
What's the number of pairs $$$(i \lt j)$$$ such that $$$d(a_i, b_i)=d(a_j, b_j)$$$, where $$$d(a_i, b_i)$$$ is the decimal representation after the decimal point of the value $$$(\frac{a_i}{b_i})$$$.
I.e. $$$d(1, 2) = 5$$$, $$$d(2, 3) = 666666\ldots$$$, $$$d(5, 2) = 5$$$.
Note that two values are equal only if they're equal to infinitely many digits.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
Then for each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 3\cdot10^5)$$$ – the number of pairs in the array.
The next $$$n$$$ lines of the case, each, contain two integers $$$a_i$$$ $$$b_i$$$ $$$(1 \leq a_i, b_i \leq 10^{18})$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases is not greater than $$$2\cdot10^6$$$.
For each test case, print one integer, the number of pairs as described in the statement.
241 22 35 211 352 34 53 924 18310 15
2 2